
#include <iostream>
#include <vector>

using namespace std;

class TrieNode {
public:
    bool is_word;
    vector<TrieNode *> children;

    TrieNode() {
        is_word = false;
        children = vector<TrieNode *>(26, nullptr);
    }

    ~TrieNode() {
        for (int i = 0; i < 26; i++) {
            if (children[i] != nullptr) {
                delete children[i];
            }
        }
    }
};

class Trie {
public:
    Trie() {
        root = new TrieNode();
    }

    ~Trie() {
        delete root;
    }

    void insert(string word) {
        TrieNode *node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (node->children[idx] == nullptr) {
                node->children[idx] = new TrieNode();
            }
            node = node->children[idx];
        }
        node->is_word = true;
    }

    bool search(string word) {
        TrieNode *node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (node->children[idx] == nullptr) {
                return false;
            }
            node = node->children[idx];
        }
        return node->is_word;
    }

    bool startsWith(string prefix) {
        TrieNode *node = root;
        for (char c : prefix) {
            int idx = c - 'a';
            if (node->children[idx] == nullptr) {
                return false;
            }
            node = node->children[idx];
        }
        return true;
    }

private:
    TrieNode *root;
};

int main() {
    Trie trie;
    trie.insert("apple");
    cout << trie.search("apple") << endl; // expected output: 1
    cout << trie.search("app") << endl; // expected output: 0
    cout << trie.startsWith("app") << endl; // expected output: 1
    trie.insert("app");
    cout << trie.search("app") << endl; // expected output: 1
    return 0;
}
//字典树（Trie Tree，也称为字典树、单词查找树、键树）是一种基于树形结构的数据结构，用于高效地存储和查找字符串。在该结构中，每个节点代表一个字符，从根节点到叶子节点的路径表示一个完整的字符串。具有相同前缀的字符串公用同一棵子树，因此可以节省大量内存，提高查询效率。字典树的基本操作包括插入一个字符串、查找一个字符串、查找所有以指定前缀为开头的字符串。
//
//以下是字典树的 C++ 实现样例，用于实现插入一个字符串、查找一个字符串和查找所有以指定前缀为开头的字符串的操作：
//
//
//
//在该代码实现中，TrieNode 类代表字典树节点，每个节点包含一个布尔型的 is_word 表示当前节点是否代表一个完整的字符串，以及一个长度为 26 的子节点数组 children，用于存储下一个可能出现的字符。Trie 类代表字典树，包含一个 TrieNode 类型的根节点 root，并且支持 insert(string word) 插入一个字符串、search(string word) 查找一个字符串和 startsWith(string prefix) 查找所有以指定前缀为开头的字符串三种基本操作。
//
//在 insert(string word) 操作中，我们首先从根节点开始遍历字符串 word 中的每个字符，查找该字符在当前节点的子节点数组 children 中的位置。若该位置为空，说明该字符尚未出现，需要新建一个 TrieNode 子节点，并将 TrieNode.is_word 标记为 false。接着，将当前节点指向该子节点，重复此过程直到遍历完整个字符串 word，最后将当前节点的 TrieNode.is_word 标记为 true，表示该节点代表一个完整的字符串。在这个过程中，如果字符串定义为空，则不做任何插入操作。
//
//在 search(string word) 操作中，也是从根节点开始遍历字符串 word 中的每个字符，查找该字符在当前节点的子节点数组 children 中的位置。若该位置为空，说明该字符串不存在，直接返回 false。若该节点标记为 TrieNode.is_word 处，表示该节点代表一个完整的字符串，则表示字符串 word 存在于字典树中，返回 true。如果遍历结束时未扫描到叶子节点，则说明该字符串的一部分已存在于字典树中，但尚未构成一个完整的字符串，因此也应该返回 false。在这个过程中，如果字符串定义为空，则不做任何查找操作，直接返回 false。
//
//在 startsWith(string prefix) 操作中，也是从根节点开始遍历字符串 prefix 中的每个字符，查找该字符在当前节点的子节点数组 children 中的位置。若该位置为空，则说明以该前缀为开头的字符串不存在于字典树中，直接返回 false。若遍历完整个字符串 prefix 时没有出现空指针，则说明以该前缀为开头的字符串存在于字典树中，返回 true。在这个过程中，如果前缀定义为空，则不做任何查找操作，直接返回 true。